package Leetcode;

/**
 * 这题就是kmp的算法，查找字符串的。
 *
 * KMP 算法就是要尽可能少的回退，以免多余的计算。
 *
 */
public class L28_StrStr {
    int[][] dp;
    int n,m;

    public int strStr(String haystack, String needle) {
        if(needle.length()==0) return 0;
        if(haystack.length()==0) return -1;
        initKmp(needle);
        return search(haystack);
    }

    public void initKmp(String pat){
        char[] p = pat.toCharArray();
        m = p.length;
        dp = new int[m][256];

        //base case
        dp[0][p[0]] = 1;
        int x = 0;//上一次最大重复的状态
        for(int i=1; i<m; i++){//i从 1开始，因为0已经有初始状态了
            for(int c=0; c < 256; c++){
                if(p[i] == c){ //只有跟当前字符相等的，才可以推进状态，不相等的都要考虑回退到 哪个状态
                    dp[i][c] = i + 1;
                }else{// 不相等的要考虑回退到上一个
                    dp[i][c] = dp[x][c];
                }
            }
            x = dp[x][p[i]];//更新，记得，这个是取上一个状态，的第i个字符的状态
        }
    }

    /**
     * 已经得到模式字符串的dp数组，来看txt里面是否有匹配的
     * dp[i][j] 表示，在状态i的时候，字符是j，对应得到什么状态
     * 如果得到的是 匹配串长度的m状态，那
     *
     */
    public int search(String txt){
        char[] t = txt.toCharArray();
        int n = t.length,i,j;

        j=0;//初始都是0
        for(i=0; i<n; i++){
            j = dp[j][t[i]];
            //到终态了
            if(j == m) return i-m+1;
        }

        return -1;
    }

    public static void main(String[] args){
        String a = "ababa";
        String b = "ababc";
        L28_StrStr l = new L28_StrStr();
        l.strStr(a, b);
    }

}
